//给定一个字符串数组 words，请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时，它们长度的乘积的最大值。假设字符串中只包含英语
//的小写字母。如果没有不包含相同字符的一对字符串，返回 0。
//
//
//
// 示例 1:
//
//
//输入: words = ["abcw","baz","foo","bar","fxyz","abcdef"]
//输出: 16
//解释: 这两个单词为 "abcw", "fxyz"。它们不包含相同字符，且长度的乘积最大。
//
// 示例 2:
//
//
//输入: words = ["a","ab","abc","d","cd","bcd","abcd"]
//输出: 4
//解释: 这两个单词为 "ab", "cd"。
//
// 示例 3:
//
//
//输入: words = ["a","aa","aaa","aaaa"]
//输出: 0
//解释: 不存在这样的两个单词。
//
//
//
//
// 提示：
//
//
// 2 <= words.length <= 1000
// 1 <= words[i].length <= 1000
// words[i] 仅包含小写字母
//
//
//
//
// 注意：本题与主站 318 题相同：https://leetcode-cn.com/problems/maximum-product-of-word-
//lengths/
// Related Topics 位运算 数组 字符串 👍 44 👎 0

package leetcode.editor.cn;

import java.util.HashMap;

@SuppressWarnings("all")
//Java：单词长度的最大乘积
public class 单词长度的最大乘积 {
    public static void main(String[] args) {
        Solution solution = new 单词长度的最大乘积().new Solution();
        // TO TEST
        String[] words = {"abcw", "baz", "foo", "bar", "fxyz", "abcdef"};
        System.out.println(solution.maxProduct(words));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int maxProduct(String[] words) {
            int res = 0;
            HashMap<String, Integer> map = new HashMap<>();
            for (int i = 0; i < words.length; i++) {
                for (int j = 1; j < words.length; j++) {
                    int len = words[i].length() * words[j].length();
                    if (len > res) {
                        int numI = get(words, map, i);
                        int numJ = get(words, map, j);
                        if ((numI & numJ) == 0) {
                            res = len;
                        }
                    }
                }
            }

            return res;
        }

        private int get(String[] words, HashMap<String, Integer> map, int i) {
            int num;
            if (map.containsKey(words[i]))
                num = map.get(words[i]);
            else {
                num = getNumber(words[i]);
                map.put(words[i], num);
            }

            return num;
        }

        private int getNumber(String word) {
            boolean[] count = new boolean[26];
            for (int i = 0; i < word.length(); i++) {
                int ch = word.charAt(i) - 'a';
                count[ch] |= true;
            }

            int res = 0;
            for (int i = 0; i < count.length; i++) {
                if (count[i])
                    res += 1 << i;
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}
